#include <stdio.h>
#include <stdlib.h>
#define VertexType int
#define VRType int
#define MAX_VERtEX_NUM 20
#define InfoType char
#define INFINITY 65535

typedef struct {
  VertexType vexs[MAX_VERtEX_NUM];
  int arcs[MAX_VERtEX_NUM][MAX_VERtEX_NUM];
  int vexnum, arcnum;
} MGraph;

int locateVex(MGraph G, VertexType v) {
  for (int i = 0; i < G.vexnum; i++) {
    if (v == G.vexs[i]) {
      return i;
    }
  }
  return -1;
}

void creatUDN(MGraph *G) {
  scanf("%d%d", &(G->vexnum), &(G->arcnum));
  for (int i = 0; i < G->vexnum; i++) {
    scanf("%d", &G->vexs[i]);
  }
  for (int i = 0; i < G->vexnum; i++) {
    for (int j = 0; j < G->vexnum; j++) {
      G->arcs[i][j] = INFINITY;
    }
  }
  for (int i = 0; i < G->arcnum; i++) {
    int v1, v2, w;
    scanf("%d%d%d", &v1, &v2, &w);
    int m = locateVex(*G, v1);
    int n = locateVex(*G, v2);
    if (m == -1 || n == -1) {
      printf("no this vertex");
      return;
    }
    G->arcs[m][n] = w;
    G->arcs[n][m] = w;
  }
}

typedef struct {
  VertexType adjvex;
  VRType lowcost;
} closedge[MAX_VERtEX_NUM];
closedge theclose;

int minimun(MGraph G, closedge close) {
  int min = INFINITY;
  int min_i = -1;
  for (int i = 0; i < G.vexnum; i++) {
    if (close[i].lowcost > 0 && close[i].lowcost < min) {
      min = close[i].lowcost;
      min_i = i;
    }
  }
  return min_i;
}

void miniSpanTreePrim(MGraph G, VertexType u) {
  int k = locateVex(G, u);
  for (int i = 0; i < G.vexnum; i++) {
    if (i != k) {
      theclose[i].adjvex = k;
      theclose[i].lowcost = G.arcs[k][i];
    }
  }
  theclose[k].lowcost = 0;
  for (int i = 1; i < G.vexnum; i++) {
    k = minimun(G, theclose);
    printf("v%d v%d\n", G.vexs[theclose[k].adjvex], G.vexs[k]);
    theclose[k].lowcost = 0;
    for (int j = 0; j < G.vexnum; j++) {
      if (G.arcs[k][j] < theclose[j].lowcost) {
        theclose[j].adjvex = k;
        theclose[j].lowcost = G.arcs[k][j];
      }
    }
  }
  printf("\n");
}

int main(void) {
  MGraph G;
  creatUDN(&G);
  miniSpanTreePrim(G, 1);
}
